public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int n = 13;
        // System.out.println((int)Math.sqrt(n));

        System.out.println(test.numSquares(n));
    }

    public int numSquares(int n) {
        /**
         * 完全平方数
         * 概念：完全平方数，即值为一个整数的二次幂
         * 状态表示：
         *  dp[i][j]表示在前i个元素中挑选，此时元素和为j，最小元素个数（若是为0则表示无法组成）
         * 状态转移方程：
         *
         * 初始化：
         *  原本打算dp[0][0]初始化为1，表示选择1个元素0，总和为0，此时最小元素个数
         *  但是从实际考虑dp[0][0] 仅在j==c时会使用到，在本题中，当j==c，即是表示元素恰好组成
         *  综上所述，本题不对该位置进行初始化，后续若是我们需要初始化时应当充分考虑到其使用情况，而不能擅自决定，切记！
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  return dp[m][n];
         * */
        // 1 预处理
        int m = (int)Math.sqrt(n);
        // 2 创建dp表
        int[][] dp = new int[m+1][n+1];
        // 3 初始化

        // 4 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                int c = i * i;
                if(j >= c && (j == c || dp[i-1][j-c] != 0 || dp[i][j-c] != 0)) {
                    int temp = Math.min(dp[i-1][j-c], dp[i][j-c]) == 0
                            ? Math.max(dp[i-1][j-c], dp[i][j-c]) + 1
                            : Math.min(dp[i-1][j-c], dp[i][j-c]) + 1;
                    // -先确定第一种情况可以组成
                    if(dp[i][j] != 0) {
                        dp[i][j] = Math.min(dp[i][j], temp);
                    } else {
                        dp[i][j] = temp;
                    }
                }
            }
        }
        // 返回值
        return dp[m][n];
    }
}
